Search and navigation in collections of complex related information can be a cumbersome process, especially in the context of business applications. There, information is often dispersed over several systems and is available in different representations and formats. Also, the relations and interdependencies of the information portion in a certain context is often either not explicitly described or not easy to find because the user has to switch between multiple systems and tools to examine different pieces of semantically connected information. Metadata information may be available in the business systems but it is typically not used for navigation and browsing across system boundaries. Interrelated representations of information are usually best visualized by graphical rendering which can also be used for interactive browsing.
There exists prior approaches for rendering relational graphs for navigation. In some of these approaches the layout is done in a restricted screen area and does not require the user to scroll to invisible parts. For example, Hyperbolic tree is a technique to map arbitrary large graphs to a hyperbolic surface, which may be a sphere applying non-Euclidian geometric transformations. Nodes and arcs in the center of the viewport are therefore larger than at the border. This means that some nodes and arcs may be in the focus of attention and others may be placed at the border of the viewpoint. This approach generally indicates to the user the relevant nodes. To see them, the user changes the focus to another area which then will be placed in the center. Due to the typical distortion effect, hyperbolic trees are also called fisheye views. Also, a tree layout algorithm is applied before the mapping is done.
Radial tree layout is another technique for rendering graphs. In this algorithm there is one node to be placed in the center of the view. All nodes that are directly linked to this node are placed concentrically on a ring around the center node. Nodes that are linked to the nodes on the first ring are placed on a second ring near the source node. This step can be recursively repeated until all nodes of the tree have been placed. The number of rings can be determined based on the available screen space. In contrast to hyperbolic trees, this means that nodes on any omitted outer rings are not displayed. The user can navigate the graph by changing the focus (clicking on a different node). In this case the selected node is placed in the center and the layout algorithm starts over. The algorithm also can be extended to show other graphs than trees (e.g. directed graphs). However, in this case there may be different possibilities to place nodes that are linked multiple times.
Spring embedder layout algorithms (also called force-directed layout or simulated annealing) have also been used to display fragments of larger graphs. The idea is to simulate the process of an annealing of liquids. Initially, the nodes receive an impulse that make them move continuously. Forces defined between the nodes constrain their movement. Linked nodes have attraction forces attached. Additionally, a smaller distraction force are added to all unlinked nodes. To prevent that the graph moves outside of the viewport a gravity force can also be used, and the viewport vector can be adjusted to the center of the graph. Temperature (impulse) is reduced to zero over time so that the graph becomes static after a while. During the start phase nodes usually find their optimal place in respect to the forces. In most cases the resulting graph layout is free of edge crossings (although there is no guarantee) and the nodes are well distributed.